package com.jp.algorithm.linkList;

public class SingleLinkList {

    Node head;

    public SingleLinkList() {
    }


    public void add(Node n) {
        Node h = head;
        head = n;
        n.next = h;
    }

    public Node delete(Node n) {
        if (head == null)
            return null;
        Node pre = null;
        Node cur = head;
        while (cur != null) {
            if (cur.item == n.item) {
                if (cur == head) {
                    head = head.next;
                } else {
                    pre.next = cur.next;
                }
                return cur;
            }
            pre = cur;
            cur = cur.next;
        }
        return null;
    }

    public void insertSort() {
        if (head == null || head.next == null)
            return;
        //分成两个链表 cur和head
        Node cur = head.next;
        head.next = null;

        while (cur != null) {

            //记录下一个节点
            Node next = cur.next;
            //清空当前节点位置
            cur.next = null;
            //当前节点小于head节点
            if (cur.item <= head.item) {
                cur.next = head;
                head = cur;
            } else { //当前节点大于head节点
                insertInOrder(head, cur);
            }
            cur = next;
        }
    }
    public Node merge(Node l1, Node l2){
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;

        Node head = l2;
        Node cur1 = l1;
        Node next1= null;

        while(cur1 != null){
            next1 = cur1.next;

            Node cur2 = head;
            while(cur2 != null){
                if(cur1.item < head.item){
                    cur1.next = head;
                    head = cur1;
                    break;
                }else if((cur1.item >= cur2.item) && (cur2.next == null || cur2.next.item >= cur1.item)){
                    cur1.next = cur2.next;
                    cur2.next = cur1;
                    break;
                }
                cur2=cur2.next;
            }
            cur1 = next1;
        }
        return head;
    }

    //有序插入,分成两个链表
    public void insertInOrder(Node head, Node n) {
        Node pre = head;
        Node cur = head.next;
        while (true) {
            if (n.item >= pre.item && (cur == null || n.item <= cur.item)) {
                pre.next = n;
                n.next = cur;
                break;
            }
            pre = cur;
            cur = cur.next;
        }
    }

    public void revertGroupByK(int k) {

        if (head == null)
            return;
        Node newHead = head;
        Node nodeK = head;
        Node pre = null;
        Node cur = head;
        Node next = null;
        Node tail = head;


        while(true){

            //定位第K个节点
            for(int i=0;i<k-1 && nodeK != null;i++){
                nodeK = nodeK.next;
            }
            //剩余节点不足K个,直接合并剩余链表
            if(nodeK == null){
                if(cur != head){
                    tail.next = cur;
                }
                break;
            }
            //新表头
            if(cur == head){
                newHead = nodeK;
            }else{ //连接下一组链表
                tail.next = nodeK;
                tail = cur;
            }

            //以K个节点为一组，反转链表，当cur为下一组的首节点退出循环
            while(pre != nodeK){
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            pre=null;
            //更新起点
            nodeK = cur;
        }
        head = newHead;

    }

    public static Node revertGroupByKRecursive(Node head, int k){
        if(head == null)
            return null;

        Node tail = head;
        Node cur = head;
        int i=0;
        for(;i<k-1 && cur!=null ;i++){
            cur = cur.next;
        }
        if(cur==null && i<k-1){
            return head;
        }

        Node pre=null;
        Node next=null;
        cur = head;

        for(int j=0;j<k;j++){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        tail.next = revertGroupByKRecursive(cur,k);

        return pre;
    }

    public Boolean isCircle() {
        if (head == null)
            return false;
        Node slow = head;
        Node fast = head;
        while (fast.next != null) {
            if (slow == fast)
                return true;
            slow = slow.next;
            fast = fast.next.next;
        }

        return false;
    }

    //逆序需要三个指针
    public void revert() {
        if (head == null || head.next == null)
            return;
        Node pre = head;
        Node cur = pre.next;
        pre.next = null;
        while (cur != null) {
            head = cur.next;
            cur.next = pre;
            pre = cur;
            cur = head;
        }
        head = pre;
    }

    //根据index获取Node
    public Node getNode(int index) {
        Node cur = head;
        while (cur != null) {
            if (index == 0)
                return cur;
            index--;
            cur = cur.next;
        }
        return null;
    }

    //有序添加
    public void addInOrder(Node n) {
        if (head == null) {
            head = n;
            return;
        }

        if (n.item <= head.item) {
            n.next = head;
            head = n;
            return;
        }
        Node pre = head;
        Node cur = head.next;

        while (true) {
            if (n.item >= pre.item && (cur == null || cur.item >= n.item)) {
                pre.next = n;
                n.next = cur;
                return;
            }
            pre = cur;
            cur = cur.next;
        }

    }

    public void print() {
        Node cur = head;
        while (cur != null) {
            System.out.println("item:" + cur.item);
            cur = cur.next;
        }
        System.out.println("===========================");
    }
    public static void printNode( Node node) {
        Node cur = node;
        while (cur != null) {
            System.out.println("item:" + cur.item);
            cur = cur.next;
        }
        System.out.println("===========================");
    }


    public static void testGroupByK()
    {
        SingleLinkList singleLinkList = new SingleLinkList();
        singleLinkList.add(new Node(9));
        singleLinkList.add(new Node(8));
        singleLinkList.add(new Node(7));
        singleLinkList.add(new Node(6));
        singleLinkList.add(new Node(5));
        singleLinkList.add(new Node(4));
        singleLinkList.add(new Node(3));
        singleLinkList.add(new Node(2));
        singleLinkList.add(new Node(1));
        singleLinkList.print();
        singleLinkList.revertGroupByK(3);
        singleLinkList.print();
    }
    public static void testGroupByKRecursive(){
        SingleLinkList singleLinkList = new SingleLinkList();
        singleLinkList.add(new Node(9));
        singleLinkList.add(new Node(8));
        singleLinkList.add(new Node(7));
        singleLinkList.add(new Node(6));
        singleLinkList.add(new Node(5));
        singleLinkList.add(new Node(4));
        singleLinkList.add(new Node(3));
        singleLinkList.add(new Node(2));
        singleLinkList.add(new Node(1));

        singleLinkList.head = revertGroupByKRecursive(singleLinkList.head,3);
        singleLinkList.print();
    }
    public static void testMerge(){
        SingleLinkList singleLinkList1 = new SingleLinkList();
        singleLinkList1.add(new Node(9));
        singleLinkList1.add(new Node(7));
        singleLinkList1.add(new Node(5));
        singleLinkList1.print();

        SingleLinkList singleLinkList2 = new SingleLinkList();
        singleLinkList2.add(new Node(8));
        singleLinkList2.add(new Node(6));
        singleLinkList2.add(new Node(4));
        singleLinkList2.print();

        Node node = singleLinkList1.merge(singleLinkList1.head,singleLinkList2.head);
        SingleLinkList.printNode(node);

    }
    public static void main(String[] args) {

        //testGroupByK();
        //testGroupByKRecursive();
        testMerge();

    }

}
